//
//  239_滑动窗口最大值.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/9.
/*
 https://leetcode.cn/problems/sliding-window-maximum/description/
 
 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

 返回 滑动窗口中的最大值 。
 
 示例 1：
 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
 输出：[3,3,5,5,6,7]
 
 示例 2：
 输入：nums = [1], k = 1
 输出：[1]
 */

import UIKit

class HuanDongWindow {
    
    func QA() {
        print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
        print(maxSlidingWindow([9,11], 2))
        print("---------------")
        print(maxSlidingWindow1([1,3,-1,-3,5,3,6,7], 3))
        print(maxSlidingWindow1([9,11], 2))

    }
//    用双端队列实现
    func maxSlidingWindow(_ nums: [Int], _ k: Int) -> [Int] {
        if nums.count == 0 || k == 0 {
            return []
        }
        if k == 1 {
            return nums
        }
        var queue = [Int]() // 双端队列（头大尾部小，依次递减）
        var resultArray = [Int]()
        for i in 0..<nums.count {
            // 删除队尾比我大的值
            while !queue.isEmpty && nums[i] >= nums[queue.last ?? 0] {
                queue.removeLast()
            }
            queue.append(i)
            
            // 检查w是否合理
            let w = i - k + 1
            if w < 0 { continue }

            // 判断队列头部是否在滑动窗口范围
            if queue[0] < w {
                queue.removeFirst()
            }
            resultArray.append(nums[queue[0]])
        }
        return resultArray
    }
    // 暴力法
    func maxSlidingWindow1(_ nums: [Int], _ k: Int) -> [Int] {
        if nums.count == 0 || k == 0 { return [] }
        if k == 1 { return nums }
        var resultArray = [Int]()
        for i in (k - 1)..<nums.count {
            let w = i - k + 1
            var maxNum = nums[w]
            for j in (w + 1)...i {
                maxNum = max(maxNum, nums[j])
            }
            resultArray.append(maxNum)
        }
        return resultArray
    }
}
